package com.chilly.vidio.study;

/**
 * 二分查找 demo
 * @author Chilly Cui
 * @createDate 2021/2/27
 */
public class BinarySearchDemo {

    public static void main(String[] args) {
        BinarySearchDemo demo = new BinarySearchDemo();
        int[] arr = {1, 5, 55, 99, 100};
        System.out.println(demo.binarySearch(arr, 5, 55));
        System.out.println(demo.binarySearch2(arr, 5, 55));
    }

    /**
     * 二分查找
     *
     * @param arr    已排好序的数组
     * @param n      数组大小
     * @param target 待查找的对象
     * @return 数组下标
     */
    private int binarySearch(int[] arr, int n, int target) {
        // 循环不变量：在[l...r]闭区间的范围里寻找target
        int l = 0;
        int r = n - 1;

        /**
         * 循环条件：只要还有查找的内容，就继续查找
         * 当l=r时，区间[l...r]依然有元素，是可查找的
         */
        while (l <= r) {
            //整型溢出：l+r
            //int mid = (l + r) / 2;
            int mid = l +(r-l)/2;
            if (arr[mid] == target) {
                return mid;
            }
            if (target > arr[mid]) {
                // 此时target在闭区间[mid+1...r]中
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 改变变量定义区间[l...r) 右区间为开区间
     */
    private int binarySearch2(int[] arr, int n, int target) {
        // 循环不变量：在[l...r) 左闭右开 区间的范围里寻找target
        int l = 0;
        int r = n;

        /**
         * 循环条件：只要还有查找的内容，就继续查找
         * 当l=r时，区间[l...r]依然有元素，是可查找的
         */
        while (l < r) {
            //取中间值
            int mid = (l + r) / 2;
            if (arr[mid] == target) {
                return mid;
            }
            if (target > arr[mid]) {
                // 此时target在闭区间[mid+1...r]中
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return -1;
    }
}
